// g++ -o test_4_15 test_4_15.cpp -lpthread

#include <linux/sched.h>
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
#include <wait.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>

#define MIN_PID 300
#define MAX_PID 5000

struct list_node{
  int val, nxt;
} * A;
int cc, SZ = 0, in[MAX_PID+1];

int allocate_map(void) {
  A = (list_node*)malloc(sizeof(list_node) * 1000005);
  cc = 0;
  for(int i = MIN_PID; i <= MAX_PID; ++ i) {
    A[++cc].val = i;
    A[cc].nxt = A[0].nxt;
    A[0].nxt = cc;
    SZ ++;
    in[i] = 0;
  }
  return 1;
}

int allocate_pid(void) {
  if(SZ == 0) return -1;
  int pid = A[A[0].nxt].val;
  A[0].nxt = A[A[0].nxt].nxt;
  SZ--;
  return pid;
}

void release_pid(int pid) {
  if(MIN_PID > pid || pid > MAX_PID) {
    printf("pid = %d not in [MIN_PID=%d,MAX_PID=%d]\n", pid, MIN_PID, MAX_PID);
    return;
  } 
  if(in[pid]) {
	  in[pid] = 0;
    A[++cc].val = pid;
    A[cc].nxt = A[0].nxt;
    A[0].nxt = cc;
  }
}
void free_map(void) {
  free(A);
}


#define NUM_THREADS 100
pthread_t tid[NUM_THREADS];
pthread_attr_t attr[NUM_THREADS];

void *runner(void *param) {
  int pid = allocate_pid();
  if(pid == -1) {
    printf("allocate pid failed");
  }
  else {
    printf("allocate pid = %d\n",pid);
    sleep(rand()%2+1);
    release_pid(pid);
    printf("release pid = %d\n",pid);
  }
  pthread_exit(0);
}

int main(int argc, char ** argv){
  if(allocate_map() == -1) {
    printf("allocate map failed\n");
    return 1;
  }

  for(int i = 0; i < NUM_THREADS; ++ i) {
    pthread_attr_init(&attr[i]);
    pthread_create(&tid[i],&attr[i],runner,NULL);
  }
  sleep(2);
  for(int i = 0; i < NUM_THREADS; ++ i) {
    if( pthread_join(tid[i],NULL) == true ) {
      printf("%d-thread join failed!\n",i);
    }
    else {
      printf("join %d-threads\n",i);
    }  
  }
  free_map();
  printf("free map\n");
	return 0;
}

